template <const int CHILD_MAX_LEN>
struct Trie {
	struct TrieNode {
		TrieNode() {
			cnt_ = 0;
			for (int i = 0; i < CHILD_MAX_LEN; i++) {
				children_[i] = nullptr;
			}
		}

		TrieNode* children_[CHILD_MAX_LEN];
		int cnt_;
	};

	void insert(const char s[]) {
		TrieNode* p = root_;
		for (int i = 0, n = strlen(s); i < n; i++) {
			int nxt = s[i] - 'a';
			if (p->children_[nxt] == nullptr) {
				p->children_[nxt] = new TrieNode();
			}
			p = p->children_[nxt];
		}
		p->cnt_++;
	}

	int query(const char s[]) {
		TrieNode* p = root_;
		for (int i = 0, n = strlen(s); i < n; i++) {
			int nxt = s[i] - 'a';
			if (p->children_[nxt] == nullptr) {
				return 0;
			}
			p = p->children_[nxt];
		}
		return p->cnt_;
	}

	int queryPrefix(const char s[]) {
		TrieNode* p = root_;
		for (int i = 0, n = strlen(s); i < n; i++) {
			int nxt = s[i] - 'a';
			if (p->children_[nxt] == nullptr) {
				return i;
			}
			p = p->children_[nxt];
		}
		return strlen(s);
	}

	void clearNode(TrieNode* current_node) {
		if (current_node == nullptr) {
			return;
		}
		for (int i = 0; i < CHILD_MAX_LEN; i++) {
			if (current_node->children_[i] != nullptr) {
				clearNode(current_node->children_[i]);
				delete current_node->children_[i];
				current_node->children_[i] = nullptr;
			}
		}
	}

	void clear() {
		clearNode(root_);
	}

	void insert(const string s) {
		insert(s.c_str());
	}

	int query(const string s) {
		return query(s.c_str());
	}

	int queryPrefix(const string s) {
		return queryPrefix(s.c_str());
	}
	TrieNode* root_ = new TrieNode();
};
int main() {
	Trie<26> tr;
	tr.insert("abc");
	tr.insert("ab");
	cout << tr.query("ab") << endl;
	tr.clear();
	cout << tr.query("ab") << endl;
	tr.insert("abc");
	cout << tr.queryPrefix("ab") << endl;
	string s = "ab";
	cout << tr.queryPrefix(s) << endl;
	tr.clear();
	cout << tr.queryPrefix(s) << endl;
	return 0;
}